package com.zlk.algorithm.huawei.nowcoder.dp;

import java.util.Scanner;
/**
 * @program: algorithm
 * @ClassName HJ52
 * @description:
 * 描述
 * https://leetcode.cn/problems/edit-distance/
 * Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。
 * 许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由
 * 俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
 * 例如：
 * 字符串A: abcdefg
 * 字符串B: abcdef
 * 通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
 * 要求：
 * 给定任意两个字符串，写出一个算法计算它们的编辑距离。
 * 数据范围：给定的字符串长度满足
 * 1≤len(str)≤1000
 * @author: slfang
 * @create: 2024-12-27 10:57
 * @Version 1.0
 **/
public class HJ52 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        //System.out.println(f1(s1, s2, 0, 0));
//        int[][] dp = new int[s1.length()+1][s2.length()+1];
//        int n = s1.length()+1;
//        int m = s2.length()+1;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                dp[i][j]=-1;
//            }
//        }
        //System.out.println(f2(s1, s2, 0, 0,dp));
        //System.out.println(f2(s1, s2));
        System.out.println(f3(s1, s2));
    }


    private static int f3(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        int[][] dp = new int[n+1][m+1];
        // dp[i][j]
        //依赖
        for (int i = 0; i <= n; i++) {
            dp[i][m] = n - i;
        }
        for (int i = 0; i <= m; i++) {
            dp[n][i] = m - i;
        }
        for (int i = n-1; i >= 0; i--) {
            for (int j = m-1; j >= 0; j--) {
                int p1 = dp[i][j + 1] + 1;
                int p2 = dp[i + 1][j + 1] + 1;
                int p3 = dp[i + 1][j] + 1;
                int min = Math.min(p1, Math.min(p2, p3));
                dp[i][j] = min;
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i+1][j+1]);
                }
            }

        }
        return dp[0][0];
    }

//    @Test
//    public void test(){
//        System.out.println(f3("abcdefgss", "abssscdefaa"));
//    }




    //递归带缓存
    private static int f2(String s1, String s2, int i, int j, int[][] dp) {
        if(dp[i][j]!=-1){
            return dp[i][j];
        }
        if(i==s1.length()){
            //删除s2 剩下的
            dp[i][j]=s2.length()-j;
            return s2.length()-j;
        }
        if(j==s2.length()){
            //删除s1剩下的
            dp[i][j] = s1.length()-i;
            return s1.length()-i;
        }
        //插入
        int p1 = f2(s1,s2,i,j+1,dp)+1;
        //替换
        int p2 = f2(s1,s2,i+1,j+1,dp)+1;
        //删除
        int p3 = f2(s1,s2,i+1,j,dp)+1;
        int min = Math.min(p1,Math.min(p2,p3));
        min = s1.charAt(i)==s2.charAt(j)?Math.min(min,f2(s1,s2,i+1,j+1,dp)):min;
        dp[i][j] = min;
        return min;
    }

    // 递归
    private static int f1(String s1, String s2, int i, int j) {
        //base case
        if(i==s1.length()){
            //删除s2 剩下的
            return s2.length()-j;
        }
        if(j==s2.length()){
            //删除s1剩下的
            return s1.length()-i;
        }
        //插入
        int p1 = f1(s1,s2,i,j+1)+1;
        //替换
        int p2 = f1(s1,s2,i+1,j+1)+1;
        //删除
        int p3 = f1(s1,s2,i+1,j)+1;
        int min = Math.min(p1,Math.min(p2,p3));
        return s1.charAt(i)==s2.charAt(j)?Math.min(min,f1(s1,s2,i+1,j+1)):min;

    }


}
